package main

import "fmt"

//动态规划0ms 100%，1.9MB 67%
func rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-1], nums[i]+dp[i-2])
	}
	return dp[len(nums)-1]

}

func max(i, j int) int {
	if i > j {
		return i
	} else {
		return j
	}
}

func main() {
	s := []int{1, 56, 36, 5}
	fmt.Println(rob(s))
}
